import java.util.LinkedList;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {

        List<Integer> list=new ArrayList();

        Stack<TreeNode> stack=new Stack();

        TreeNode cur=root;
        while(cur!=null||!stack.isEmpty()){
            while(cur!=null){

                stack.push(cur);
                cur=cur.left;
            }

            TreeNode top=stack.pop();
            list.add(top.val);
            cur=top.right;


        }

        return list;





    }

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */


    class Solution {
        public List<List<Integer>> levelOrderBottom(TreeNode root) {
            Queue<TreeNode> queue=new LinkedList<>();
            List<List<Integer>> list=new ArrayList();


            if(root==null){
                return list;
            }

            queue.add(root);


            while(!queue.isEmpty()){
                int size=queue.size();
                List<Integer> list1=new ArrayList();
                for(int i=0;i<size;i++){
                    TreeNode top=queue.poll();
                    list1.add(top.val);

                    if(top.left!=null)
                        queue.add(top.left);

                    if(top.right!=null)
                        queue.add(top.right);


                }

                list.addFirst(list1);

            }

            return list;



        }
    }
}